/*================================================================
*   Copyright (C) 2024 baichao All rights reserved.
*
*   文件名称：main.c
*   创 建 者：baichao
*   创建日期：2024年01月08日
*   描    述：
*
================================================================*/

/*
 * 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序
 * ，返回矩阵中的所有元素。
 *
 * 示例 1：
 *   输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
 *   输出：[1,2,3,6,9,8,7,4,5]
 *
 * 示例 2：
 *   输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
 *   输出：[1,2,3,4,8,12,11,10,9,5,6,7]
 *
 *
 * 提示：
 *   m == matrix.length
 *   n == matrix[i].length
 *   1 <= m, n <= 10
 *   -100 <= matrix[i][j] <= 100
 */

#include <stdio.h>
#include <stdlib.h>

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
/*
 * 思路很简单：就是观察螺旋轨迹得到:y_min->y_max;x_min->x_max;y_max->y_min;x_max->x_min。
 */
int* spiralOrder(int** matrix, int matrixSize, int* matrixColSize,
                 int* returnSize) {
  int m = matrixSize;
  int n = *matrixColSize;
  int totalSize = m * n;
  int* ret = (int*)malloc(totalSize * sizeof(int));

  int x_min = 0, y_min = 0;
  int x_max = m - 1, y_max = n - 1;
  int ret_index = 0;

  while (ret_index < totalSize) {
    // 从左到右
    for (int j = y_min; j <= y_max; j++) {
      ret[ret_index++] = matrix[x_min][j];
    }
    x_min++;

    // 从上到下
    for (int i = x_min; i <= x_max; i++) {
      ret[ret_index++] = matrix[i][y_max];
    }
    y_max--;

    // 从右到左
    if (ret_index < totalSize) {
      for (int j = y_max; j >= y_min; j--) {
        ret[ret_index++] = matrix[x_max][j];
      }
      x_max--;
    }

    // 从下到上
    if (ret_index < totalSize) {
      for (int i = x_max; i >= x_min; i--) {
        ret[ret_index++] = matrix[i][y_min];
      }
      y_min++;
    }
  }

  *returnSize = totalSize;
  return ret;
}

int main() {
  int matrixData[][3] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
  int matrixSize = sizeof(matrixData) / sizeof(matrixData[0]);
  int matrixColSize = 3;

  int* matrix[matrixSize];
  for (int i = 0; i < matrixSize; i++) {
    matrix[i] = matrixData[i];
  }

  int retSize = 0;
  int* ret = spiralOrder(matrix, matrixSize, &matrixColSize, &retSize);

  printf("Modified Matrix:\n");
  for (int i = 0; i < retSize; i++) {
    printf("%d ", ret[i]);
  }
  printf("\n");

  free(ret);

  return 0;
}